{-# LANGUAGE TupleSections #-}

-- |
-- Module: Data.Vector.Mutable.Sized.Shuffle
-- Copyright: (c) 2018 Koz Ross
-- Maintainer: Koz Ross <koz.ross@retro-freedom.nz>
-- Stability: Experimental
-- Portability: Non-portable
--
-- Implementation of Fisher-Yates shuffling for fixed-length arrays. This does
-- an in-place shuffle of a mutable vector.
module Data.Vector.Mutable.Sized.Shuffle
  ( fisherYates
  ) where

import Control.Monad.Primitive
import Control.Monad.Random
import Data.Foldable
import GHC.TypeNats

import qualified Data.Vector.Generic.Mutable as VGM
import qualified Data.Vector.Generic.Mutable.Sized as VGMS

-- | Shuffles the input mutable fixed-length vector.
--
-- __Complexity:__ \(O(n)\)
{-# INLINE fisherYates #-}
fisherYates ::
     (MonadRandom m, PrimMonad m, KnownNat n, VGM.MVector v a)
  => VGMS.MVector v n (PrimState m) a
  -> m ()
fisherYates vec = do
  ixes <- traverse (getRandomR . (0, )) [0 .. VGMS.length vec - 2]
  traverse_ (uncurry (VGMS.unsafeSwap vec)) $ zip [0 ..] ixes
